/**
 * 矩阵连乘最优计算次数问题
 * 矩阵乘法是满足乘法交换律的，因此对矩阵连乘中不同位置加上括号会带来不同的计算次序
 * 而不同的计算次序会导致计算量的不同，如何确定最优计算次序呢？
 * - 穷举法：计算所有可能加括号的方式，然后一一尝试，直到找到最优的计算次序，但是这样是指数时间复杂度
 * - 如何使用动态规划来解决矩阵连乘最优计算次序的问题呢？
 */



 // 矩阵连乘问题的递归算法（重复处理子问题）
 /**
  * 
  * @param {*} p 矩阵数组
  * @param {*} i 矩阵起始位置下标
  * @param {*} j 矩阵结束位置下标
  */
 function matrixChainOrder_r(p, i, j) {
    if (i == j) return 0
    let k, min = 1000000, count
    for (k = i; k < j; k++) {
        count = matrixChainOrder(p, i, k) + matrixChainOrder(p, k + 1, j) + p[i - 1]*p[k]*p[j]
        if (count < min) {
            min = count
        }
    }
    return min
 }


 // 改进，使用动态规划
function matrixChainOrder_d(p) {
    let m = [], s = [], n = p.length // m 用来存储最优值；s用来存储最优解（即最优的计算次序）
    let i, j, k, L, q
    // 自底向上求解子问题
    for (i = 1; i < n; i++) { 
        m[i] = []
        m[i][i] = 0
    }
    for (j = 2; j < n; l++) { // 逐步扩大子问题的规模
        for (i = 1; i <= n - j + 1; i++) { // 划分矩阵连乘的计算范围
            j = i + j - 1
            m[i][j] = -1
            s[i][j] = i
            for (k = i; k <= j - 1; k++) { // 在确定的连乘范围内，依次加上括号来对比计算量，得到最小的加括号位置
                q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j]
                if (q < m[i][j]) {
                    m[i][j] = q
                    s[i][j] = k
                }
            }
        }
    }
    return m[1][n - 1] // 返回最优值
}